/**
 * 
 */
package com.gwcloud.leetcode.interview100;

/**
 * @ClassName   : Leetcode0204 
 * @author      : ganwei 
 * @date        : 2020年5月29日
 * @Description : Leetcode0204 计数质数
 */
public class Leetcode0204 {
	/**
	 * -解题思路
	 */
    public int countPrimes(int n) {
    	int result = 0;
    	boolean[] b = new boolean[n+1];
    	if(n > 2){
    		result ++;
    	}
    	
    	for(int i = 3; i < n; i += 2){
    		if(!b[i]){
    			for(int j = 3; i*j < n; j += 2){
    				b[i*j] = true;
    			}
    			result++;
    		}
    	}
    	
    	return result;
    }
}
